/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        121.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 15:03
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
//你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
//返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
#include "../header.h"

class Solution {
public:
    int maxProfit(vector<int> &prices) {
//        int n = prices.size();
//        int dp[n][2]; //[天数][1=>持有/ 0=>未持有]
//        // 初始化
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for (int i = 1; i < n; ++i) {
//            dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
//            dp[i][1] = max(dp[i - 1][1] , - prices[i]);
//        }
//        return dp[n-1][0];
        int n = prices.size();
        // 初始化
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        for (int i = 0; i < n; ++i) {
            dp_i_0 = max(dp_i_1 + prices[i], dp_i_0);
            dp_i_1 = max(-prices[i], dp_i_1);
        }
        return dp_i_0;
    }
};
